﻿using System;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmInterview.Chapter01._01;

/// <summary>
/// 方法一：就地逆序
/// </summary>
public class Test01
{
    /// <summary>
    /// 对单链表进行逆序
    /// </summary>
    /// <param name="head">指向链表头结点的引用</param>
    public static void Reverse(LNode head)
    {
        // 判断链表是否为空
        if (head == null) return;
        LNode pre = null;   // 前驱结点
        LNode cur = null;   // 当前结点
        LNode next = null;  // 后续结点

        // 把链表首结点变为尾结点
        cur = head.next;
        next = cur.next;
        cur.next = null;
        pre = cur;
        cur = next;

        // 使当前遍历到的结点cur指向其前驱结点
        while (cur.next != null)
        {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        // 结点最后一个结点指向倒数第二个结点
        cur.next = pre;
        // 链表的头结点指向原来链表的尾结点
        head.next = cur;
    }

    public static void Main(string[] args)
    {
        int i = 0;
        // 链表头结点
        LNode head = new LNode();
        head.next = null;
        LNode tmp = null;
        LNode cur = head;
        // 构造单链表
        for (; i < 8; i++)
        {
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        Console.Write("逆序前：");
        for (cur = head.next; cur != null; cur = cur.next)
        {
            Console.Write(cur.data + " ");
        }

        Console.Write("逆序后：");
        Reverse(head);
        for (cur = head.next; cur != null; cur = cur.next)
        {
            Console.Write(cur.data + " ");
        }

    }

}


